/****************************************************************
 * Linklist.c:
 * Linklist.h的实现(貌似应该是线程安全的)
 * **************************************************************/

#include "Linklist.h"
#include <stdlib.h>
#include <string.h>

llist_t		*lklst_init( )
{

	llist_t		*phead = (llist_t *)malloc(sizeof(llist_t));

	if(phead == NULL)
		return NULL;
	
	phead->total_num = 0;
	phead->rd_counter = 0;
	phead->first = phead->last = NULL;
	
	if(sem_init(&(phead->mutex), 0, 1) != 0)
	{
		free(phead);
		return NULL;
	}

	if(sem_init(&(phead->wr_sem), 0, 1) != 0)
	{
		free(phead);
		return NULL;
	}

	return phead;
}

llist_t		*lklst_del_by_addr(llist_t *head, lnode_t *willdel);
char		IfInTheList(llist_t *head, lnode_t *thisnode);

llist_t		*lklst_destroy(llist_t *head)
{
	if(head == NULL)
		return NULL;

	sem_wait(&(head->wr_sem));				//LOCK
	llist_t head_backup;
	/**********************************************************************************\
	 * 为head作个备份,这样就可以只修改head的各域,然后解锁,这样在其他线程看来,已经为空了
	 * 这样可以避免链表过大,销毁时间过长,占用锁太久,如果销毁过程出错还可以及时恢复
	 * <..死锁了......貌似semaphore不能随便备份....先暂搁一下这个功能>
	\**********************************************************************************/
	memcpy(&head_backup, head, sizeof(llist_t));
	//head->total_num = 0;
	//head->first = head->last = NULL;

	/*****暂搁一下*******
	sem_wait(&(head_backup.wr_sem));		//仍然有必要锁住此备份
	int		succ_flag = 1;
	
	while(head_backup.first != NULL)
	{
		if(lklst_del_by_addr(&head_backup, head_backup.last) != &head_backup)
		{
			succ_flag = 0;
			break;
		}
	}
	
	if(succ_flag == 0)
	{//恢复head
		sem_wait(&(head->wr_sem));	//LOCK
		memcpy(head, &head_backup, sizeof(llist_t));
		sem_post(&(head->wr_sem));	//UNLOCK
	}
	sem_post(&(head_backup.wr_sem));			//解锁head的备份

	if(succ_flag == 0)
		return NULL;
	else
		return head;
	*/
	
	while(head->first != NULL)
	{
		if(lklst_del_by_addr(head, head->last) != head)
			break;
	}

	sem_post(&(head->wr_sem));				//UNLOCK
	return head;
}

lnode_t		*lklst_insert(llist_t *head, void *to_insert, const size_t datasize)	
{
	if(!(((long)head) && ((long)to_insert)))
		return NULL;

	lnode_t		*newnode = (lnode_t *)malloc(sizeof(lnode_t));
	if(newnode == NULL)
		return NULL;
	if( (newnode->dataptr = malloc(datasize)) == NULL)
		return NULL;
	memcpy(newnode->dataptr, to_insert, datasize);
	
	newnode->prior = NULL;
	newnode->DataSize = datasize;

	sem_wait(&(head->wr_sem));					//Must I lock the list from here?

	if(head->total_num != 0)
	{
		head->first->prior = newnode;
	}
	else
		head->last = newnode;
	newnode->next		= head->first;
	(head->total_num)	++;
	head->first			= newnode;
	
	sem_post(&(head->wr_sem));					//unlock

	return newnode;
}

lnode_t		*lklst_walkthrough(llist_t *head, lnode_t *start_pos, void *to_cmp, int (*fcmp)(void *data1, void *data2))
{//private function , usually used by lklst_delete() and lklst_query(), because they are so similar,
	//this is NOT thread-safe(为了避免死锁),所以只应该被此文件中的函数以安全方式调用
	
	lnode_t *dest = head->first ;
	char find_flag = 0;

	if(start_pos != NULL)
	{//try to find if it's in the list
		if((find_flag = IfInTheList(head, start_pos)) == 1)
			dest = start_pos->next;
		else
			dest = head->first;
	}

	/***********开始根据参数to_cmp查找匹配,如果匹配则返回匹配的结点地址,否则NULL********/
	find_flag = 0;
	while(dest != NULL)
	{
		if(fcmp(dest->dataptr, to_cmp) == 0)
		{
			find_flag = 1;
			break;
		}
		dest = dest->next;
	}
	if(find_flag == 1)
		return dest;
	else
		return NULL;
}

llist_t		*lklst_del_by_addr(llist_t *head, lnode_t *willdel)
{//根据要删除的结点地址来删除,供lklst_delete()和lklst_destroy()调用
	//(也不是安全的(不是线程安全,所以应该只被本文件中的函数以安全方式调用)

	if(IfInTheList(head, willdel) != 0)
		free(willdel->dataptr);
	else 
		return NULL;

	if(head->total_num == 1)
	{//如果仅此一个结点
		head->first = head->last = NULL;
	}
	else if(head->first == willdel)	
	{//排除以上情况,如果要删除的结点是first,则后续结点的prior要改为null, head->first也需要改变
		willdel->next->prior = NULL;
		head->first = willdel->next;
	}
	else if(willdel->next == NULL)
	{//排除以上情况,如果此结点是最后一个,则前驱的next要改为NULL, head->last也需要修改
		head->last = willdel->prior;
		willdel->prior->next = NULL;
	}
	else
	{//要删除的节点在中间.......
		willdel->prior->next = willdel->next;
		willdel->next->prior = willdel->prior;
	}
	(head->total_num) --;
	
	free(willdel);

	return head;
}

llist_t		*lklst_delete(llist_t *head, void *to_del, int (*fcmp)(void *data1, void *data2))
{
	if( !(((long)head) && ((long)to_del) && (long)fcmp ))
		return NULL;
	sem_wait(&(head->wr_sem));				//lock		

	lnode_t	*willdel = lklst_walkthrough(head, NULL, to_del, fcmp);
	llist_t *ItsNotHead = lklst_del_by_addr(head, willdel);

	sem_post(&(head->wr_sem));		//unlock
	return ItsNotHead;
}

lnode_t		*lklst_query(llist_t *head, lnode_t *start, void *to_query, int(*fcmp)(void *data1, void *data2))
{
	if(! ((long)head && (long)to_query && (long)fcmp))
		return NULL;
	lnode_t	*ret;

	sem_wait(&(head->mutex));
	(head->rd_counter) ++;

	if(head->rd_counter == 1)
		sem_wait(&(head->wr_sem));

	sem_post(&(head->mutex));
	ret = lklst_walkthrough(head, start, to_query, fcmp);

	sem_wait(&(head->mutex));
	(head->rd_counter) --;

	if(head->rd_counter == 0)
		sem_post(&(head->wr_sem));

	sem_post(&(head->mutex));

	return ret;

}

llist_t		*lklst_delete_all(llist_t *head, void *to_del, int (*fcmp)(void *data1, void *data2))
{
	
	if( !(((long)head) && ((long)to_del) && (long)fcmp ))
		return NULL;
	sem_wait(&(head->wr_sem));				//lock		

	lnode_t	*willdel;
	llist_t *ItsReallyNotHead;

	while(willdel = lklst_walkthrough(head, NULL, to_del, fcmp) != NULL)		//这里可以优化一下
		ItsReallyNotHead = lklst_del_by_addr(head, willdel);

	sem_post(&(head->wr_sem));				//unlock
	return ItsReallyNotHead;
}

void	*lklst_get_content(llist_t *head, lnode_t *nodeaddr, void *content)
{
	lnode_t *pnode;
	char	find_flag = 0;

	if( ! (((long)head) && ((long)nodeaddr) && ((long)content) && head->total_num ))
		return NULL;
	pnode = head->first;
	
	sem_wait(&(head->mutex));				//LOCK
	if( ++(head->rd_counter) == 1)
		sem_wait(&(head->wr_sem));
	sem_post(&(head->mutex));

	if((find_flag = IfInTheList(head, nodeaddr)) == 1)
		memcpy(content, pnode->dataptr, pnode->DataSize);

	sem_wait( &(head->mutex));				//UNLOCK
	if( --(head->rd_counter) == 0)
		sem_post( &(head->wr_sem));
	sem_post( &(head->mutex));
	
	return ( (find_flag == 1) ? content : NULL);

}

char	IfInTheList(llist_t *head, lnode_t *thisnode)
{//也不是线程安全的,仅供内部使用
	char	find_flag = 0;
	lnode_t	*pnode;
	if(head == NULL || head->total_num == 0 || thisnode == NULL)
		return 0;

	pnode = head->first;
	while(pnode != NULL)
	{
		if(pnode == thisnode)
		{
			find_flag = 1;
			break;
		}
		
		pnode = pnode->next;
	}

	return find_flag;
}
